import io
class Peeker:
    """Wrapper for stdin that implements proper peeking"""
    def __init__(self, fileobj:io.TextIOWrapper):
        self.fileobj = fileobj
        self.buf = io.StringIO()
    def _append_to_buf(self, contents):
        oldpos = self.buf.tell()
        self.buf.seek(0, io.SEEK_END)
        self.buf.write(contents)
        self.buf.seek(oldpos)
    def _buffered(self):
        oldpos = self.buf.tell()
        data = self.buf.read()
        self.buf.seek(oldpos)
        return data
    def fileno(self):
        return self.fileobj.fileno()
    def kbhit(self):
        import os, sys, tty, fcntl, termios
        fd = self.fileno()
        old_settings = termios.tcgetattr(fd)
        old_fl = fcntl.fcntl(fd, fcntl.F_GETFL)
        try :
            tty.setraw(sys.stdin.fileno())
            fcntl.fcntl(fd, fcntl.F_SETFL, old_fl | os.O_NONBLOCK)
            hit = self.peek(1)
            if not bool(hit) : self.buf.read(1)
        finally : 
            fcntl.fcntl(fd, fcntl.F_SETFL, old_fl)
            termios.tcsetattr(fd, termios.TCSADRAIN, old_settings)
        return bool(hit)
    def getch(self):
        import sys, tty, termios
        fd = sys.stdin.fileno()
        old_settings = termios.tcgetattr(fd)
        try:
            tty.setraw(sys.stdin.fileno())
            ch = self.read(1)
        finally:
            termios.tcsetattr(fd, termios.TCSADRAIN, old_settings)
        return ch
    def peek(self, size):
        buf = self._buffered()[:size]
        if len(buf) < size:
            contents = self.fileobj.read(size - len(buf))
            self._append_to_buf(contents)
            return self._buffered()
        return buf
    def read(self, size=None):
        import io
        if size is None:
            contents = self.buf.read() + self.fileobj.read()
            self.buf = io.StringIO()
            return contents
        contents = self.buf.read(size)
        if len(contents) < size:
            contents += self.fileobj.read(size - len(contents))
            self.buf = io.StringIO()
        return contents
    def readline(self):
        import io
        line = self.buf.readline()
        if not line.endswith('\n'):
            line += self.fileobj.readline()
            self.buf = io.StringIO()
        return line
    def close(self):
        self.buf = None
        return self.fileobj


class _Getch:
    def __init__(self):
        try:
            self.impl = _GetchWindows()
        except ImportError:
            self.impl = _GetchUnix()
    def __call__(self): return self.impl()

class _GetchUnix:
    def __init__(self):
        import sys
        if type(sys.stdin) != Peeker:
            sys.stdin = Peeker(sys.stdin)
    def __call__(self):
        import sys
        return sys.stdin.getch()

class _GetchWindows:
    def __init__(self):
        import msvcrt
    def __call__(self):
        import msvcrt
        return msvcrt.getch()

getch = _Getch()

class _Kbhit:
    def __init__(self):
        try:
            self.impl = _KbhitWindows()
        except ImportError :
            self.impl = _KbhitUnix()
    def __call__(self):return self.impl()

class _KbhitUnix:
    def __init__(self):
        import sys
        if type(sys.stdin) != Peeker:
            sys.stdin = Peeker(sys.stdin)
    def __call__(self):
        import sys
        return sys.stdin.kbhit()

class _KbhitWindows:
    def __init__(self):
        import msvcrt
    def __call__(self):
        import msvcrt
        return msvcrt.kbhit()

kbhit = _Kbhit()

import signal

def after_timeout():  # 超时后的处理函数
    print("timeout!")

def timeout(num, callback=after_timeout):
    def wrap(func):
        def handle(signum, frame):  # 收到信号 SIGALRM 后的回调函数，第一个参数是信号的数字，第二个参数是the interrupted stack frame.
            raise RuntimeError
        def to_do(*args, **kwargs):
            try:
                signal.signal(signal.SIGALRM, handle)  # 设置信号和回调函数
                signal.alarm(num)  # 设置 num 秒的闹钟
                r = func(*args, **kwargs)
                signal.alarm(0)  # 关闭闹钟
                return r
            except RuntimeError as e:
                callback()
        return to_do
    return wrap

